// 19. Remove Nth Node From End of List

// Given a linked list, remove the nth node from the end of list and return its head.

// For example,
//    Given linked list: 1->2->3->4->5, and n = 2.
//    After removing the second node from the end, the linked list becomes 1->2->3->5.

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	if head == nil {
		return head
	}

	h, rm, i := head, head, 0
	for h != nil {
		h = h.Next
		if i > n {
			rm = rm.Next
		}
		i++
	}

	if i <= n {
		head = head.Next
		return head
	}

	if n == 1 {
		rm.Next = nil
		return head
	}

	rm.Next, rm.Next.Next = rm.Next.Next, nil
	return head
}

func (l *ListNode) printNode() {
	i := 1
	for l != nil {
		println("i=", i, "v=", l.Val)
		l = l.Next
		i++
	}
}

func main() {
	h, i := new(ListNode), 1
	head := h
	for i < 3 {
		h.Val = i
		h.Next = new(ListNode)
		h = h.Next
		i++
	}
	h.Val = i

	head.printNode()
	head = removeNthFromEnd(head, 3)
	println("==========")
	head.printNode()
}
